package likou;

import java.util.*;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/04/26 09:10
 */
class Onece {
    int count;//当前的总重量
    List<Integer> weights;//当前的包裹
}

public class _1011 {
    /**
     * 使用暴力合并法，得出答案。包括答案的组合。
     * @param weights
     * @param D
     * @return
     */
    public static int shipWithinDays(int[] weights, int D) {
        List<Onece> nowList = new ArrayList<>();
        int res = 0;
        int count = 0;
        for (int i : weights) {
            res = Math.max(i, res);
            count += i;
        }
        res = Math.max(res, count / D);

        //初始化nowList，第一次分区
        Onece onece = new Onece();
        onece.weights = new ArrayList<>();
        for (int i = 0; i < weights.length; i++) {
            if (nowList.size() < D) {
                if (onece.count + weights[i] <= res) {
                    onece.count += weights[i];
                    onece.weights.add(weights[i]);
                } else {
                    nowList.add(onece);
                    onece = new Onece();
                    onece.weights = new ArrayList<>();
                    i--;
                }
            } else {
                onece.count += weights[i];
                onece.weights.add(weights[i]);
                if (i == weights.length - 1) {
                    nowList.add(onece);
                }
            }
        }
        while (nowList.size() > D) {
            res++;
            //把后面的移入前面的
            for (int i = 0; i < nowList.size() - 1; i++) {
                int p = i;
                while (nowList.get(p+1).count==0){
                    p++;
                }
                while (p < nowList.size() - 1 && nowList.get(i).count + nowList.get(p + 1).weights.get(0) <= res) {
                    int next = nowList.get(p + 1).weights.get(0);
                    nowList.get(i).count += next;
                    nowList.get(i).weights.add(next);
                    nowList.get(p + 1).count -= next;
                    nowList.get(p + 1).weights.remove(0);
                    if (nowList.get(p + 1).count == 0) {
                        p++;
                    }
                    System.out.println(p);
                }
                if (nowList.get(nowList.size() - 1).count == 0) {
                    return res;
                }
            }
        }
        return res;
    }


    /**
     * 使用二分查找法，找答案！
     * @param weights
     * @param D
     * @return
     */
    public int shipWithinDays2(int[] weights, int D) {
        // 载重范围，最小应该是货物中最大重量（否则就没办法装船了）
        int left = 0;
        for (int weight : weights) {
            if (weight > left) {
                left = weight;
            }
        }
        // 最大应该是假设每个货物都为最大，平均每天能带多少
        // 注：当D > weights.length 时, right < left 即 此时会直接返回 left。而背后的逻辑是，当天数大于货物数量，那么只要每天至少搬一个货物上船即可，此时可以达到区间的最小，即货物的最大重量
        int right = left * weights.length / D + 1;
        // 取值区间使用左右闭合
        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (canFinish(weights, D, mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean canFinish(int[] weights, int D, int cap) {
        int day = 1, cur = cap;
        for (int weight : weights) {
            if (weight > cur) {
                day++;
                cur = cap;
            }
            cur -= weight;
        }
        return day <= D;
    }

    public static void main(String[] args) {
//        System.out.println(shipWithinDays(new int[]{380, 374, 65, 345, 170, 427, 256, 53, 241, 500, 262, 444, 36, 411, 209, 371, 428, 400, 359, 182, 272, 278, 219, 219, 14, 176, 185, 243, 240, 425, 402, 488, 460, 100, 433, 278, 472, 153, 444, 386, 282, 118, 13, 358, 489, 291, 249, 343, 207, 11, 184, 245, 473, 104, 279, 490, 74, 386, 269, 296, 284, 301, 163, 486, 206, 255, 264, 119, 216, 279, 369, 347, 322, 177, 102, 60, 313, 279, 339, 363, 192, 101, 164, 108, 300, 238, 290, 338, 153, 61, 368, 348, 291, 333, 354, 341, 146, 158, 301, 185, 354, 233, 157, 377, 431, 496, 70, 367, 459, 224, 80, 151, 79, 164, 327, 452, 418, 409, 171, 365, 398, 396, 249, 269, 448, 346, 196, 163, 476, 189, 185, 398, 283, 400, 331, 459, 483, 299, 68, 78, 327, 356, 14, 148, 133, 319, 327, 348, 422, 307, 454, 301, 177, 35, 412, 118, 88, 267, 476, 218, 61, 380, 486, 256, 274, 23, 156, 9, 62, 426, 32, 209, 434, 469, 335, 173, 356, 231, 374, 168, 24, 498, 212, 333, 74, 31, 121, 467, 89, 92, 154, 97, 115, 412, 126, 38, 347, 118, 498, 111, 6, 374, 362, 316, 418, 474, 382, 423, 326, 334, 463, 176, 12, 66, 327, 362, 109, 307, 96, 312, 329, 133, 370, 421, 169, 231, 268, 321, 34, 425, 375, 469, 29, 266, 199, 279, 221, 292, 4, 416, 118, 194, 342, 257, 194, 261, 493, 334, 259, 287, 38, 70, 415, 486, 73, 324, 360, 15, 360, 288, 296, 441, 50, 284, 137, 150, 310, 363, 414, 493, 456, 18, 425, 211, 343, 45, 47, 457, 310, 267, 475, 427, 374, 148, 31, 308, 389, 384, 285, 12, 331, 462, 264, 249, 80, 107, 181, 310, 423, 319, 98, 143, 42, 444, 486, 99, 455, 219, 150, 29, 264, 456, 481, 427, 500, 78, 470, 350, 376, 233, 221, 480, 32, 358, 266, 161, 431, 450, 334, 415, 398, 167, 147, 337, 298, 406, 493, 56, 293, 464, 123, 93, 457, 425, 102, 76, 65, 40, 151, 29, 414, 497, 199, 89, 187, 177, 126, 45, 141, 454, 206, 472, 72, 152, 3, 80, 284, 33, 410, 409, 361, 353, 15, 261, 228, 403, 105, 309, 424, 259, 326, 191, 229, 250, 264, 374, 68, 1, 85, 218, 497, 173, 271, 453, 468, 241, 386, 238, 25, 220, 29, 398, 276, 427, 73, 138, 433, 177, 334, 50, 145, 238, 295, 70, 463, 407, 210, 307, 432, 265, 494, 375, 244, 253, 116, 274, 242, 302, 382, 85, 32, 179, 371, 387, 121, 129, 169, 107, 53, 67, 353, 292, 472, 337, 99, 161, 279, 24, 399, 305, 98, 65, 301, 252, 280, 54, 190, 160, 11, 471, 329, 132, 397, 298, 251, 437, 376, 152, 239, 408, 70, 465, 107, 422, 234, 200, 272, 312, 21, 81, 34, 323, 94, 489, 138, 57, 303, 314, 67, 310, 145, 212, 258, 500, 360, 365, 253, 3, 317, 494, 371, 18, 154, 436, 14, 184, 49, 280, 4, 264, 398, 371, 404, 81, 488, 86, 294, 211, 448, 107, 18, 464, 42, 474, 113, 187, 406, 353, 230, 357, 260, 385, 170, 119, 389, 203, 364, 174, 47, 464, 439, 31, 445, 369, 255, 327, 141, 159, 72, 324, 220, 52, 295, 178, 213, 460, 394, 211, 222, 173, 72, 127, 134, 384, 11, 341, 285, 6, 97, 224, 268, 220, 327, 439, 358, 375, 269, 330, 120, 248, 228, 186, 465, 457, 402, 305, 155, 322, 474, 332, 308, 274, 305, 478, 178, 331, 330, 356, 340, 177, 415, 347, 206, 372, 246, 108, 61, 301, 465, 53, 413, 86, 90, 497, 41, 399, 400, 212, 374, 397, 272, 320, 109, 166, 284, 389, 272, 239, 260, 274, 265, 77, 52, 366, 283, 97, 107, 308, 327, 8, 347, 316, 100, 163, 311, 111, 363, 180}, 324));
        List<Integer> li = new ArrayList<Integer>(){
            {
                System.out.println(123);
            }
            @Override
            public boolean add(Integer integer) {
                System.out.println("add "+integer);
                return super.add(integer);
            }
        };
        li.add(1);
        System.out.println(li.getClass());
    }
}
